{ "nbformat": 4, "nbformat_minor": 0, "metadata": { "colab": { "name": "Final (Solved).ipynb", "provenance": [] }, "kernelspec": { "name": "python3", "display_name": "Python 3" }, "language_info": { "name": "python" } }, "cells": [ { "cell_type": "markdown", "metadata": { "id": "vYKL_0UiiNSm", "pycharm": { "name": "#%% md\n" } }, "source": [ "# Invincible Nutritional Supplements\n", "## Problem Definition\n", "Invincible Ltd makes two types of nutritional supplements. The recip of both supplements is based on three ingredients for which the company has limited availability. The table below shows the daily availability of the three ingredients and their costs:\n", "\n", "**Table 1:** daily availability and cost of ingredients\n", "\n", "| Ingredient | Availability (grams) | Cost (€cents/gram) | \n", "|------------|----------------------|--------------------|\n", "| 1 | 1500 | 85 |\n", "| 2 | 1300 | 90 |\n", "| 3 | 2000 | 125 |\n", "\n", "The selling prices are 3€/gram for supplement Awesome (product A) and 3.5€/gram for supplement Beast (product B). \n", "\n", "The recip must comply with the following requirements:\n", "\n", "- Both products must contain at least 25% of ingredient 3. \n", "\n", "- Product B must have at least 10% more of ingredient 2 than product A.\n", "\n", "- The minimum quantity of any ingredient in any product is 10%\n", "\n", "The factory has a production line that operates for 10 hours per day. The production speed of the line is 300 grams per hour for product A and 175 grams per hour for product B.\n", "\n", "### Indices\n", "We can define the following indices to express the problem in a compact form:\n", "- i: Ingredient $i \\in [1, 2, 3]$\n", "\n", "- j: Product $j \\in [A, B]$ \n", "\n", "### Decision variables\n", "The decision variables are: \n", "\n", "$x_{ij}$: Amount of ingredient i (1, 2, 3) in product j: A, B (ie i=[1,2,3], j=[A,B]) in grams\n", "\n", "### Objective Function\n", "The objective function is:\n", "\n", "$\\max z = \\sum_{i=1}^{3}\\sum_{j=A}^{B}(d_j - c_i)*x_{ij}$\n", "\n", "where $d_j$ is the selling price of a gram of product j and $c_i$ is the cost of ingredient i.\n", "\n", "$\\max z=(3-0.85)*x_{1A}+(3-0.9)*x_{2A}+(3-1.25)*x_{3A})+(3.5-0.85)*x_{1B}+(3.5-0.9)*x_{2B}+(3.5-1.25)*x_{3B}$\n", "\n", "$\\max z=2.15*x_{1A}+2.1*x_{2A}+1.75*x_{3A}+2.65*x_{1B}+2.6*x_{2B}+2.25*x_{3B}$\n", "\n", "\n", "### Constraints\n", "Subject to the following constraints:\n", "\n", "Availability constraints\n", "The availability constraints can be expressed in a compact form as: \n", "\n", "$\\sum_jx_{ij} \\leq a_i \\quad \\forall i$ \n", "\n", "$x_{1A}+x_{1B} \\leq 1500$ \n", "\n", "$x_{2A}+x_{2B} \\leq 1300$\n", "\n", "$x_{3A}+x_{3B} \\leq 2000$\n", "\n", "Both products must contain at least 25% of ingredient 3\n", "\n", "$x_{3A} \\geq 0.25*(x_{1A}+x_{2A}+x_{3A})$\n", "\n", "$x_{3B} \\geq 0.25*(x_{1B}+x_{2B}+x_{3B})$\n", "\n", "Product B must have at least 10% more of ingredient 2 than product A:\n", "\n", "$x_{2B} \\geq 1.1(x_{2A})$\n", "\n", "The minimum quantity of any ingredient in any product is 10%:\n", "\n", "??\n", "\n", "Production capacity constraint:\n", "\n", "??\n", "\n", "A solver provides the following tables with the solution of the primal and the dual: \n", "\n", "\n", "| Variables | Solution (GRB) | Reduced cost (GRB) | Objective Coefficient (GRB) | Objective Lower bound (GRB) | Objective Upper bound (GRB) |\n", "|:-----------------------------------|---------------:|-------------------:|----------------------------:|----------------------------:|----------------------------:|\n", "| Grams of ingredient 1 in product A | 1460.65 | 0 | 2.15 | 1.75 | 132.4 |\n", "| Grams of ingredient 1 in product B | 39.35 | 0 | 2.65 | -inf | 3.58 |\n", "| Grams of ingredient 2 in product A | 232.54 | 0 | 2.1 | -inf | 2.63 |\n", "| Grams of ingredient 2 in product B | 255.79 | 0 | 2.6 | -inf | 3.09 |\n", "| Grams of ingredient 3 in product A | 632.2 | 0 | 1.75 | 1.61 | 2.15 |\n", "| Grams of ingredient 3 in product B | 98.38 | 0 | 2.25 | -inf | 3.05 |\n", " \n", "\n", "| idx | Constraint | Right Hand Side | Shadow Price | Slack | Min RHS | Max RHS |\n", "|----:|:-----------------------------------------------------------|----------------:|-------------:|---------:|--------:|--------:|\n", "| 0 | Ingredient 1 availability | 1500 | 0.4 | 0 | 271.89 | 1550.85 |\n", "| 1 | Ingredient 2 availability | 1300 | 0 | 811.67 | 488.33 | inf |\n", "| 2 | Ingredient 3 availability | 2000 | 0 | 1269.42 | 730.58 | inf |\n", "| 3 | Ingredient 3 >=25% in product_A | 0 | 0 | -50.85 | -inf | 50.85 |\n", "| 4 | Ingredient 3 >=25% in product_B | 0 | -1.04 | 0 | -50.07 | 42.04 |\n", "| 5 | Product B >=10% of ingredient 2 than product A | 0 | -0.69 | 0 | -330 | 42.04 |\n", "| 6 | Quantity of ingredient 1 in product A must be at least 10% | 0 | 0 | -1228.11 | -inf | 1228.11 |\n", "| 7 | Quantity of ingredient 1 in product B must be at least 10% | 0 | -1.04 | 0 | -35.16 | 242.68 |\n", "| 8 | Quantity of ingredient 2 in product A must be at least 10% | 0 | -0.41 | 0 | -300 | 21.82 |\n", "| 9 | Quantity of ingredient 2 in product B must be at least 10% | 0 | 0 | -216.44 | -inf | 216.44 |\n", "| 10 | Quantity of ingredient 3 in product A must be at least 10% | 0 | 0 | -399.66 | -inf | 399.66 |\n", "| 11 | Quantity of ingredient 3 in product B must be at least 10% | 0 | 0 | -59.03 | -inf | 59.03 |\n", "| 12 | Production capacity | 10 | 512.58 | 0 | 9.67 | 15.69 |\n", "\n", "\n", "**a** Write the expressions of the missing constraints. You may use indices to write your expressions in a compact form \n", "\n", "The minimum quantity of any ingredient in any product is 10%, this means that the quantity of ingredient i in product j must be at least 10% of the total amount of ingredients used for product j, which is the sum of the three ingredients: \n", "\n", "$x_{ij} \\geq 0.1*(x_{1j} + x_{2j} + x_{3j}) \\quad \\forall i, j$\n", "\n", "As for the production capacity constraint, let us express the production speed for product j $v_j$ as the ratio between the quantity of product j produced and the production time of product j, $t_j$ in hours: \n", "\n", "$v_j = \\frac{\\text{grams of product j}}{\\text{production hours j}} = \\frac{x_{1j} + x_{2j} + x_{3j}}{t_j}$ \n", "\n", "Now, the problem states that the production speeds are $v_A = 300$ grams/hour and $v_B = 175$ grams/hour. The problem also states that the production time available is 10 hours, that is:\n", "\n", "$t_A + t_B \\leq 10$ \n", "\n", "Plugging in the expressions for the speeds and the values given yields:\n", "\n", "$\\frac{x_{1A}+x_{2A}+x_{3A}}{300}+\\frac{x_{1B}+x_{2B}+x_{3B}}{175} \\leq 10$\n", "\n", "**b** Write down the objective function of the dual problem and provide an economic interpretation of the dual variables \n", "\n", "The objective coefficients of the dual are the same as the RHS of the primal and are given in the RHS column given by the solver:\n", " \n", "$\\min z* = 1500*u_1 + 1300*u_2 + 2000*u_3 + 10*u_{12}$\n", "\n", "- $u_1$: Shadow price of the availability of constraint 1 (non-negative). It indicates the increase in the objective function per every additional gram of ingredient 1. \n", "- $u_2$: Shadow price of the availability of constraint 1 (non-negative). It indicates the increase in the objective function per every additional gram of ingredient 2.\n", "- $u_3$: Shadow price of the availability of constraint 1 (non-negative). It indicates the increase in the objective function per every additional gram of ingredient 3.\n", "- $u_4$: Shadow price of the quality requirement that the quantity of ingredient 3 must be higher than 25% in product A (non-positive). It indicates the decrease in the objective function if the required amount of ingredient 3 increases\n", "- $u_5$: Shadow price of the quality requirement that the quantity of ingredient 3 must be higher than 25% in product B (non-positive). It indicates the decrease in the objective function if the required amount of ingredient 3 increases\n", "- $u_6 - u_{11}$: Shadow price of the quality requirement that the quantity of any ingredient in any product must be higher than 10% (non-positive). It indicates the decrease in the objective function if the minimum amount required increases\n", "- $u_{12}$: Shadow price of the production line capacity constraint (non-negative) It indicates the increase in the objective function for any additional hour of production capacity in the line\n", "\n", "**c** What is the maximum price for ingredient 3 that the company can pay without changes in the optimal solution? Motivate your response \n", "\n", "The coefficient of $x_{3A}$ can decrease at most 14€ cents (from 1.75 to 1.61 euros) without changing the optimal solution. Since this coefficient is the price of product A minus the cost of ingredient 3, this is the maximum increase in the price of ingredient 3 without changes in the optimal solution. Thus, the maximum price is 139€cents. \n", "\n", "**d** The company can improve the daily capacity of the line in 1 hour for 50000€. How would this affect the profits and how long will it take for the company to make this investment profitable, considering only the increase in the daily profits \n", "\n", "The daily profits would increase in 512.58 euros. The company would need: \n", "\n", "$\\frac{50000}{512.8} = 97.5$\n", "\n", "operation days to return this investment with the additional profits obtained\n", "\n", "\n", "**e** Is the availability of ingredient 1 a binding constraint? How would you optimise the procurement of ingredients (daily amounts that are available) according to the provided solution? **(2 points)**\n", "\n", "The constraint is binding because the slack is zero. \n", "The company can reduce the availability of ingredient 2 in 811.67 grams and the availability of ingredient 3 in 1269.42 grams " ] } ] }